// https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
// Created by ade on 2022/11/15.
// 你有 k 个 非递减排列 的整数列表。找到一个 【最小】 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
//
// 我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
// 输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
// 输出：[20,24]
// 解释：
// 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
// 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
// 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    // 滑动窗口解法：
    // 参考：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solution/pai-xu-hua-chuang-by-netcan/
    vector<int> smallestRange1(vector <vector<int>> &nums) {
        vector <pair<int, int>> q = {};//first-队列号 second-值
        for (int i = 0; i < nums.size(); i++) {
            for (auto &j:nums[i]) {
                q.push_back({i, j});
            }
        }
        sort(q.begin(), q.end(), [&](pair<int, int> &a, pair<int, int> &b) {
            return a.second < b.second;
        });
        vector<int> res = {};
        unordered_map<int, int> m = {};
        int left = 0;
        for (int i = 0; i < q.size(); i++) {
            m[q[i].first]++;
            // 精髓在这里，不用关心具体窗口滑动的过程，只需要关系滑动完成的状态,这样代码会简单很多
            while (m[q[left].first] > 1) {
                m[q[left].first]--;
                left++;
            }
            if (m.size() == nums.size()) {
                if (res.empty() || q[i].second - q[left].second < res[1] - res[0]) {
                    res = vector < int > {q[left].second, q[i].second};
                }
            }
        }

        return res;
    }

    // 多路并归
    vector<int> smallestRange(vector <vector<int>> &nums) {
        // vector<int> 0-横坐标 1-纵坐标 2-值
        auto cmp = [&](vector<int> &a, vector<int> &b) {
            return a[2] > b[2];
        };
        priority_queue < vector < int > , vector < vector < int >>, decltype(cmp) > pq(cmp);
        vector<int> maxElem = {-1, -1, -1};
        for (int i = 0; i < nums.size(); i++) {
            pq.push({i, 0, nums[i][0]});
            if (maxElem[0] == -1 || maxElem[2] < nums[i][0]) {
                maxElem = {i, 0, nums[i][0]};
            }
        }

        vector<int> res = {pq.top()[2], maxElem[2]};
        int i = 0;
        while (1) {
            auto top = pq.top();
            if (maxElem[2] - top[2] < res[1] - res[0]) res = {top[2], maxElem[2]};
            if (top[1] >= nums[top[0]].size() - 1) break; // 数组的长度不一致，这里需要注意，防止内存溢出
            pq.pop();
            int val = nums[top[0]][top[1] + 1];
            pq.push({top[0], top[1] + 1, val});
            if (val > maxElem[2]) {
                maxElem = {top[0], top[1] + 1, val};
            }
        }
        return res;
    }
};

int main() {
    Solution so;
    vector <vector<int>> nums = {{4, 10, 15, 24, 26},
                                 {0, 9,  12, 20},
                                 {5, 18, 22, 30}};
    auto res = so.smallestRange(nums);
    cout << res[0] << '-' << res[1] << endl;
    return 0;
}